#include <stdio.h>
void HeapAdjust(int a[],int s,int m)//一次筛选的过程
{
    int rc,j;
    rc=a[s];
    for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选
    {
        if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标
        if(rc>a[j]) break;
        a[s]=a[j];s=j;
    }
    a[s]=rc;//插入
}
void heap_sort(int a[],int n)
{
    int temp,i,j;
    for(i=n/2;i>0;i--)//通过循环初始化顶堆
    {
        HeapAdjust(a,i,n);
    }
    for(i=n;i>0;i--)
    {
        temp=a[1];
        a[1]=a[i];
        a[i]=temp;//将堆顶记录与未排序的最后一个记录交换
        HeapAdjust(a,1,i-1);//重新调整为顶堆
    }
}

void QuickSortMain(int *arr, int low, int high)
{
    if (low < high){
        int i = low;
        int j = high;
        int k = arr[low];
        while (i < j){
            while(i < j && arr[j] >= k){     // 从右向左找第一个小于k的数
                j--;
            }

            if(i < j){
                arr[i++] = arr[j];
            }

            while(i < j && arr[i] < k){      // 从左向右找第一个大于等于k的数
                i++;
            }

            if(i < j){
                arr[j--] = arr[i];
            }
        }

        arr[i] = k;

        // 递归调用
        QuickSortMain(arr, low, i - 1);     // 排序k左边
        QuickSortMain(arr, i + 1, high);    // 排序k右边
    }
}

void quick_sort(int unsorted_array[], int num_elements){
    int i;
    QuickSortMain(unsorted_array, 0, num_elements-1);  // 快速排序
    for(i = 0; i < num_elements; i++)
    {
        printf("%-3d", unsorted_array[i]);
    }
    printf("\n");
}

void insertion_sort(int unsorted_array[], int num_elements){
    int i,j,temp;
    for(i = 0;i < num_elements;i++){
        temp = unsorted_array[i]; //待排序的元素
        for(j = i - 1;j >= 0 && unsorted_array[j] > temp;j--){
            unsorted_array[j+1] = unsorted_array[j];
        }
        unsorted_array[j+1] = temp;
    }
}
int main()
{
    int a[] = {1,9,8,7,6,5,0,2,3,4};
    insertion_sort(a, 10);

    printf("插入排序为:");
    for(int i=0; i<10; i++) {
        printf("%3d ", a[i]);
    }

    printf("\n"); //  此时应该看到输出为 0 1 2 3 4 5 6 7 8 9

    // 定义 int c[], int d[]，并初始化，用于测试quick_sort和heap_sort
    int b[] = {1,9,6,7,89,5,0,99,77,4};

    heap_sort(b,10);
    printf("堆排序为:");
    for(int i=1;i<=10;i++)
    {
        printf("%d   ",b[i]);
    }

    printf("\n");

    int c[] = {1,6,8,7,45,5,9,2,3,4};

    printf("快速排序为:");
    quick_sort(c,10);
}